package org.basis.algorithm.sort;

import org.basis.algorithm.common.SortUtil;

/**
 * 快排2.0版本
 *
 * @author Mr_wenpan@163.com 2021/12/06 15:20
 */
public class QuickSort2 {

    public static void main(String[] args) {
        int[] arr = {1, 30, 22, 90, 20, 77, 33, 55, 66, 8, 5, 9, 3, 0, 10, 7, 2, 3, 9, 8, 2, 2, 5, 1, 2, 4, 5};
        quickSort(arr);
        SortUtil.printArr(arr);
    }

    private static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        doQuickSort(arr, 0, arr.length - 1);
    }

    private static void doQuickSort(int[] arr, int left, int right) {
        // base case
        if (left >= right) {
            return;
        }
        // 分区
        int[] partition = partition(arr, left, right);
        // 小于区
        doQuickSort(arr, left, partition[0]);
        // 大于区
        doQuickSort(arr, partition[1], right);
    }

    /**
     * 分区方法
     */
    private static int[] partition(int[] arr, int left, int right) {
        int i = left - 1;
        int j = right;
        int index = left;

        // 优化时间复杂度为O（N*logN），随机选取一个数来放到最后一位
        SortUtil.swap(left + (int) (Math.random() * (right - left + 1)), right, arr);

        // 边界条件能否取等
        while (index < j) {
            if (arr[index] < arr[right]) {
                SortUtil.swap(index++, ++i, arr);
            } else if (arr[index] > arr[right]) {
                // index不往前走
                SortUtil.swap(index, --j, arr);
            } else {
                index++;
            }
        }

        // 交换最后一个位置
        SortUtil.swap(right, index, arr);

        return new int[]{i, j};
    }
}
